1. Field of the Invention
The present invention relates to a method and apparatus for multiplying two elements in the finite field GF(2.sup.m).
2. Description of the Related Art
As explained fully in European application No. 0080528 from which the following discussion is taken, the finite field GF(2.sup.m) is a number system containing 2.sup.m elements. Its attractiveness in practical applications results from the ability to represent each element by a vector of m binary digits. The practical application of error-correcting codes makes considerable use of computation in GF(2.sup.m). Both the encoding and decoding devices for the important Reed-Solomon codes must perform computations in GF(2.sup.m). The decoding device for the binary Bose-Chaudhuri-Hocquenghem codes also must perform computation in GF(2.sup.m). The reader is referred to "Error-Correcting Codes" by W. W. Peterson and E. J. Weldon, Jr., 2nd Ed., the M.I.T. Press, 1972, for details of these and other applications of GF(2.sup.m) computation for error-correction.
There exist cryptographic systems with encryption and decryption algorithms that require exponentiation operations on large numbers. Several public-key cryptosystems have been proposed that require or may be adapted to use the exponentiation of elements in GF(2.sup.m). Since the process of exponentiation consists of squaring and multiplication operations, it is essential that these operations be performed as quickly and efficiently as possible. The reader is referred to "Cryptography and Data Security" by D. E. Denning, Addison-Wesley, 1983, for desriptions of GF(2.sup.m) arithmetic and exponentiation algorithms, and for examples of public-key cryptosystems utilizing these algorithms. Recent advances in the art of secrecy coding also require the use of computation in GF(2.sup.m). The reader is referred to the letter "Implementing Public Key Scheme", by S. Berkovits, J. Kowalchuk and B. Schanning, IEEE Communications Magazine, Vol. 17, pp. 2-3, May 1979.
The finite field GF(2) is the number system in which the only elements are the binary numbers 0 and 1 and in which the rules of addition and multiplication are the following: EQU 0+0=1+1=0 EQU 0+1=1+0=1 EQU 0.times.0=1.times.0=0.times.1=0 (1) EQU 1.times.1=1
These rules are commonly called modulo-two arithmetic. Hence all additions specified in logic expressions or by adders in this application are performed modulo two. In addition, multiplication is implemented with logical AND gates to correspond with the rule set out at (1) above. The finite field GF(2.sup.m), where m is an integer greater than 1, is the number system in which there are 2.sup.m elements and in which the rules of addition and multiplication correspond to arithmetic modulo an irreducible polynomial of degree m with coefficients in GF(2). Although in an abstract sense there is for each m only one field GF(2.sup.m), the complexity of the logic circuitry required to perform operations in GF(2.sup.m) depends strongly on the particular way in which the field elements are represented.
The conventional approach to the design of logic circuitry to perform operations in GF(2.sup.m) is described in such papers as T. Bartee and D. Schneider, "Computation with Finite Fields", Information and Control, Vol. 6, pp. 79-98, 1963. In this conventional approach, one first chooses a polynomial P(X) of degree m which is irreducible over GF(2), that is P(X) has binary coefficients but cannot be factored into a product of polynomials with binary coefficients each of whose degree is less than m. An element A in GF(2.sup.m) is then defined to be a root of P(X), that is, to satisfy P(A)=0. The fact that P(X) is irreducible guarantees that the m elements A.sup.0 =1, A, A.sup.2, . . . , A.sup.m-1 of GF(2.sup.m) are linearly independent over GF(2), that is, that b.sub.0 +b.sub.1 A+b.sub.2 A.sup.2 + . . . +b.sub.m-1 A.sup.m-1 vanishes only when the binary digits b.sub.0,b.sub.1,b.sub.2 . . . , b.sub.m-1 are all zeroes. The conventional approach is then to assign the unit vectors of length m with binary components to the elements, 1, A, A.sup.2, . . . , A.sup.m-1.
As a specific example of the conventional approach, consider the finite field GF(2.sup.3) with the choice EQU P(X)=X.sup.3 +X+1 (2)
for the irreducible polynomial of degree 3. The next step is to define A as an element of GF(2.sup.3) such that EQU A.sup.3 +A+1=0 (3)
The following assignment of unit vectors is then made: EQU A.sup.0 =1=[0, 0, 1] EQU A=[0, 1, 0] EQU A.sup.2 =[1, 0, 0] (4)
An arbitrary element B of GF(2.sup.3) is now represented by the binary vector [b.sub.2, b.sub.1, b.sub.0 ] with the meaning that EQU B=[b.sub.2,b.sub.1,b.sub.0 ]=b.sub.2 A.sup.2 +b.sub.1 A+b.sub.0 ( 5)
Let C=[c.sub.2,c.sub.1,c.sub.0 ] be a second element of GF(2.sup.3). It follows from equations (4) and (5) that EQU B+C=[b.sub.2 +c.sub.2,b.sub.1 +c.sub.1,b.sub.0 +c.sub.0 ]. (6)
Thus, in the conventional approach, addition in GF(2.sup.m) is easily performed by logic circuitry that merely forms the modulo-two sum of the two vectors representing the elements to be summed component-by-component. Multiplication is, however, considerably more complex to implement. Continuing the example, one sees from equation (3) that EQU A.sup.3 =A+1 EQU A.sup.4 =A.sup.2 +A (7)
where use has been made of the fact that -1=+1 in GF(2). From the equations (4), (5) and (7) it follows that EQU B.times.C=[d.sub.2, d.sub.1, d.sub.0 ] (8)
where EQU d.sub.0 =b.sub.0 c.sub.0 +b.sub.1 c.sub.2 +b.sub.2 c.sub.1 EQU d.sub.1 =b.sub.0 c.sub.1 +b.sub.1 c.sub.0 +b.sub.1 c.sub.2 +b.sub.2 c.sub.1 +b.sub.2 c.sub.2 ( 9) EQU d.sub.2 =b.sub.0 c.sub.2 +b.sub.2 c.sub.0 +b.sub.1 c.sub.1 +b.sub.2 c.sub.2
Complex logic circuitry is required to implement equations (9). Upon taking C=B equation (8), it follows from equation (9) that EQU B.sup.2 =[e.sub.2, e.sub.1, e.sub.0 ] (10)
where EQU e.sub.0 =b.sub.0 EQU e.sub.1 =b.sub.2 ( 11) EQU e.sub.2 =b.sub.1 +b.sub.2
and where use has been made of the facts that b.sup.2 =b and b+b=0 in GF(2). Whereas the squaring rule of equations (11) is considerably simpler to implement than the multiplication rule of equations (9), it still has the disadvantage that some additions (in the example, only one) must be performed and that the form of the squaring rule varies among the components of the square.
By way of summary, one can say that the conventional approach to the design of logic circuitry to perform operations in GF(2.sup.m) leads to simple circuitry for addition, somewhat more complex circuitry for squaring, and very complex circuitry for multiplication.
In the European application No. 0080528 noted above advantage was taken of the following special features of the finite field GF(2.sup.m). There always exists a so-called normal basis for this finite field, that is, one can always find a field element A such that A, A.sup.2, A.sup.4, . . . , A.sup.2.spsp.m-1 are a basis for GF(2.sup.m) in the sense that every field element B can be uniquely written as ##EQU1## where b.sub.0, b.sub.1, b.sub.2, . . . , b.sub.m-1 are binary digits. Moreover, squaring in GF(2.sup.m) is a linear operation in the sense that for every pair of elements B and C in GF(2.sup.m) EQU (B+C).sup.2 =B.sup.2 +C.sup.2 ( 13)
Further, it is the case for every element B of GF(2.sup.m) that EQU B.sup.2.spsp.m =B (14)
The inventors in the above application sought to simplify the multiplication procedure by initially choosing a polynomial P(X) of degree m which is irreducible over GF(2) and which has linearly independent roots. This latter condition on P(X) insures that upon defining A as an element of GF(2.sup.m) such that P(A)=0 then A, A.sup.2, A.sup.4, . . . A.sup.2.spsp.m-1 form a normal basis for GF(2.sup.m).
For a discussion of normal bases in finite fields, the reader is referred to "Finite Fields" by Lidl and Neidereiter. Then if B=[b.sub.m-1, . . . , b.sub.2, b.sub.1, b.sub.0 ] and C=[c.sub.m-1, . . . , c.sub.2, c.sub.1, c.sub.0 ] are any two elements of GF(2.sup.m) in said normal basis representation, then the product EQU D=BXC=[d.sub.m-1, . . . , d.sub.2, d.sub.1, d.sub.0 ] (15)
has the property that the same logic circuitry which when applied to the components or binary digits of the vectors representing B and C produces d.sub.m-1 will sequentially produce the remaining components d.sub.m-2, . . . , d.sub.2, d.sub.1, d.sub.0 of the product when applied to the components of the successive rotations of the vectors representing B and C.
This may be appreciated by considering the binary digits d.sub.2, d.sub.1, d.sub.0 of e.g. equation (9) above where EQU d.sub.2 =b.sub.1 c.sub.1 +b.sub.0 c.sub.1 +b.sub.1 c.sub.0 +b.sub.0 c.sub.2 +b.sub.2 c.sub.0 EQU d.sub.1 =b.sub.0 c.sub.0 +b.sub.2 c.sub.0 +b.sub.0 c.sub.2 +b.sub.2 c.sub.1 +b.sub.1 c.sub.2 EQU d.sub.0 =b.sub.2 c.sub.2 +b.sub.1 c.sub.2 c+b.sub.2 c.sub.1 +b.sub.1 c.sub.0 +b.sub.0 c.sub.1
Like ones of one of the binary digits b.sub.i or c.sub.i are grouped to obtain grouped terms so that these may be rewritten in the form EQU d.sub.2 =b.sub.0 (c.sub.1 +c.sub.2)+c.sub.0 (b.sub.1 +b.sub.2)+b.sub.1 c.sub.1 EQU d.sub.1 =b.sub.2 (c.sub.0 +c.sub.1)+c.sub.2 (b.sub.0 +b.sub.1)+b.sub.0 c.sub.0 EQU d.sub.0 =b.sub.1 (c.sub.2 +c.sub.0)+c.sub.1 (b.sub.2 +b.sub.0)+b.sub.2 c.sub.2
Where an expression such as b.sub.0 (c.sub.1 +c.sub.2) is subsequently referred to as a grouped term. Thus the logic equation for d.sub.1 could be derived from that for d.sub.2 by reducing the suffix of all binary digits b.sub.i, c.sub.i, by 1 (Modulo-3). A practical implementation was achieved by entering the vectors in respective shift registers, establishing connections and implementing digital logic circuitry to generate all terms of the component d.sub.2 simultaneously. Then the shift register contents are rotated one bit position to obtain d.sub.1, and, similarly d.sub.0. Thus, by rotating the vectors B and C in the two shift registers, the binary digits of the product vector D could be generated by the one logic circuit.
However, whilst the above proposal is more efficient than the conventional approach, it suffers the disadvantage that all grouped terms constituting one binary digit of the vector must be added simultaneously at one location. This makes the implementation of the logic complicated, and for large values of m, (e.g. greater than 250), impractical. The above European application also proposes the simultaneous or parallel generation of all m binary digits of the product vector by m identical multiplier logic circuits. However, this simply compounds the difficulty of logic implementation because of the increase in external shift register connections and the large amount of circuitry required.